1. Field of the Invention
The present invention relates generally to a decoding apparatus and method in a communication system, and in particular, to an apparatus and method for performing turbo decoding.
2. Description of the Related Art
In digital communication systems, forward error correction (FEC) codes are generally used to effectively correct an error which may occur on a channel during data transmission. This increases the reliability of data transmission. Forward error correction codes include a turbo code. Since the turbo code, compared with a convolutional code, has superior error correction capability during high-speed data transmission, it has been adopted in both a synchronous Code Division Multiple Access 2000 (CDMA2000) system and an asynchronous Universal Mobile Telecommunications System (UMTS) both of which are attracting public attention as a third generation mobile communication system.
FIG. 1 is a block diagram illustrating an example of a receiver in a third generation mobile communication system. FIG. 1 shows a structure of a receiver in, for example, a Evolution Data and Voice (1×EV-DV) system which enables high-speed packet data communication.
In FIG. 1, a received signal is subjected to Radio Frequency (RF), Intermediate Frequency (IF) and baseband processing by a reception signal processor 10. A signal processed by the reception signal processor 10 is separated according to channels. A receiver 30 processes a forward fundamental channel (F-FCH) signal, a forward supplemental channel (F-SCH) signal, and a forward dedicated control channel (F-DCCH) signal. A receiver 40 processes a forward packet data channel (F-PDCH) signal. A receiver 50 processes a forward packet data control channel (F-PDCCH). The receiver 40 includes blocks 42, 44, 46 and 48. The block 42 has a function of minimizing a loss which may occur on a channel, and includes a finger and a combiner (both of which are not shown). The block 44 has a function of converting a signal so as to enable channel decoding, and includes a demodulation buffer, a Walsh decover, a symbol demapper and a descrambler (all of which are not shown). The block 48 has a function of performing decoding and providing the decoding result to an L1 layer 70 for its reference, and includes a turbo decoder and an output buffer (both of which are not shown). The block 46 has a function of delivering a demodulation symbol to the block 48, for decoding, and includes a combiner, a deshuffler, a deinterleaver, and a memory buffer (all of which are not shown).
A searcher 20 is an element for searching a received signal, and a (HARQ) Hybrid Automatic Repeat Request (HARQ) controller 60 is an element for requesting retransmission of a reception-failed symbol.
FIG. 2 is a block diagram illustrating an example of a conventional turbo decoder apparatus, and in particular, illustrates an example of a detailed structure of the turbo decoder block 48 shown in FIG. 1. In the drawing, the turbo decoder is constructed with, for example, a Soft-In Soft-Out (SISO) scheme. The turbo decoder can also be implemented using a (MAP) Maximum A Posteriori (MAP) scheme or a Register Exchange Soft Output Viterbi Algorithm (RESOVA) scheme instead of the SISO scheme. The SISO scheme is a scheme for calculating probability with reliability for a symbol, and the RESOVA scheme is a scheme for calculating probability for a codeword by considering a path over which a symbol passes as a long codeword.
Referring to FIG. 2, symbols (data bits) stored in a memory buffer 46-1 of the block 46 illustrated in FIG. 1 are provided to an input terminal of the block 48. In the memory buffer 46-1, a systematic code, which is a systematic code of interleaved bits, and a parity code #1 and a parity code #2, which are non-systematic codes of the interleaved bits, are separately stored. Bits of the systematic code and bits of the parity codes are simultaneously provided from the memory buffer 46-1 to the block 48. For example, in a 1×EV-DV system, the memory buffer 46-1 is a Quasi-Complementary Turbo Code (QCTC) memory buffer for storing symbols received from a transmitter after being encoded with a QCTC code. Since one code output from the memory buffer 46-1 is comprised of M bits and three codes of systematic code and parity codes Parity#1 and Parity#2 are all output from the memory buffer 46-1, a 3×M-bit bus is formed between the memory buffer 46-1 and the block 48, and codes output from the memory buffer 46-1 are provided to a multiplexer (MUX) 48-1 of the block 48.
The turbo decoder block 48 includes the multiplexer 48-1, a SISO decoder (or a decoder for the SISO scheme) 48-2, an interleaver 48-3, a deinterleaver 48-4, an output buffer 48-5, and a Cyclic Redundancy Code (CRC) checker 48-6. The multiplexer 48-1 multiplexes bits from the memory buffer 46-1, an output of the interleaver 48-3 and an output of the deinterleaver 48-4. The SISO decoder 48-2 SISO-decodes an output of the multiplexer 48-1, using the construction illustrated in FIG. 3. The interleaver 48-3 interleaves an output of the SISO decoder 48-2, and the deinterleaver 48-4 deinterleaves an output of the SISO decoder 48-2. The output buffer 48-5 stores the deinterleaving result of the deinterleaver 48-4 so that the L1 layer processor 70 can refer to the deinterleaving result. The CRC checker 48-6 performs CRC check on the deinterleaving result by the deinterleaver 48-4, and provides the CRC check result to the L1 layer processor 70.
FIG. 3 is a block diagram illustrating an example of a conventional SISO decoder. The drawing shows an example in which a SISO decoder is released with a sliding window mode scheme, and it is assumed herein that the number of windows is 2. The SISO decoder is identical to the MAP decoder (or a decoder for the MAP scheme) in basic structure and different from the MAP decoder in only output value.
Referring to FIG. 3, the SISO decoder calculates several metrics in its decoding process. That is, during a decoding operation of the SISO decoder, a delta metric, an alpha (α) metric, a beta (β) metric, and log likelihood ratio (LLR) values are calculated. A demultiplexer (DEMUX) 205 accesses data bits stored in the memory buffer 46-1 at a predetermined rate, i.e., a rate three times higher than a clock (or operating frequency) of the turbo decoder, and provides a first output (1), a second output (2) and a third output (3). A delta metric calculation section 210 includes three calculators 211 to 213, which calculate delta metrics for the first to third outputs (1) to (3), respectively. An alpha metric calculator 220 receives the delta metric calculated by the delta metric calculator 211 and calculates an alpha metric corresponding thereto. A beta metric calculation section 230 is comprised of two calculators 231 and 232, and a multiplexer 233. That is, the beta metric calculation section 230 includes the calculator 231 for calculating a first beta (β1) metric, the calculator 232 for calculating a second beta (β2) metric, and the multiplexer 233 for multiplexing the calculation results by the calculators 231 and 232. An LLR calculation section 240 is comprised of three calculators 241 to 243, and receives the alpha metric calculated by the alpha metric calculator 220 and the multiplexing result by the multiplexer 233 and calculates LLR values corresponding thereto. A subtraction section 250 is comprised of three subtracters 251 to 253, which subtract the first output (1) of the demultiplexer 205 from the LLR values calculated by the LLR calculators 241 to 243, and provide the subtraction result to the interleaver 48-3 and the deinterleaver 48-4 illustrated in FIG. 2, for interleaving/deinterleaving.
As described above, the conventional SISO decoder is comprised of the delta metric calculation section, the alpha metric calculation section and the beta metric calculation section, for metric calculation, and the LLR calculation section for decoding the metrics based on probability. Here, the beta metric calculation section is comprised of two calculators according to the number of the windows.
The delta metric, also known as “state metric,” represents transition probability from one state to another state of an encoder. The α metric, also known as “forward state metric,” represents the sum of a metric of a probability value to be transitioned from a previous state to the next state and a metric of a probability value to become a previous state. The α metric refers to accumulation probability over a period of a signal calculated from a first received signal, and is sequentially calculated. The β metric, also known as “backward state metric,” represents accumulation probability from a current state to a previous state. If the α metric and the β metric are both calculated, then a value of LLR is calculated. LLR represents probability for a symbol, and expresses a ratio of probability of “1” to probability of “0” in a log scale. The LLR calculators 241 to 243 for calculating LLR each calculate probability for a symbol based on transition probability for a forward state and a reverse state. Here, an LLR value with a positive number represents a symbol “1,” while an LLR value with a negative number represents a symbol “0.” In order to decode a signal received in this way, the SISO decoder calculates both an α metric value and a β metric value. Here, since the β metric value must be calculated in opposite order of a received signal stored in the memory buffer 46-1, an LLR value cannot be cannot be calculated until calculation of the β metric is completely ended.
FIGS. 4A and 4B are block diagrams illustrating examples of metric calculation order by the conventional SISO decoder of FIG. 3. Specifically, FIG. 4A shows a process of calculating an α metric, while FIG. 4B shows a process of calculating a β metric. Referring to FIGS. 4A and 4B, it is noted that the process of calculating an α metric is different from the process of calculating a β metric. An α metric αk is calculated from a (k−1)th α metric, which is a previous value, while a β metric βk is calculated from a (k+1)th β metric, which is a next value. In order to calculate a β metric in this way, a received signal must be referred to in the opposite order in which it was received, causing an initial delay by the entire length of the received signal.
FIGS. 5A and 5B are block diagrams illustrating an example of the calculation order in a frame mode and a window mode by the conventional SISO decoder of FIG. 3. Specifically, FIG. 5A shows the order of calculating metrics in a frame mode by the SISO decoder 48-2, while FIG. 5B shows the order of calculating metrics in a window mode shown in FIG. 3 by the SISO decoder 48-2.
Referring to FIG. 5A, since an α metric and an LLR value λ are calculated after a β metric is completely calculated, an initial delay occurs in a frame period. A SISO decoder with such a frame mode scheme calculates an LLR value λ by calculating an α metric after calculating a β metric. Therefore, a delay time occurs during calculation of a β metric. In order to reduce such an initial delay, a sliding window mode scheme has been proposed.
Referring to FIG. 5B, a SISO decoder 48-2 in a window mode divides a received signal in a predetermined length in order to calculate a β metric. If a β metric is calculated with a received signal divided in a predetermined length, initially calculated values have incorrect probability, but more correct values are calculated as time goes by. Actually, when LLR is calculated, a value calculated from a period where a correct value is calculated can be used. Here, for the convenience of calculation, lengths of an incorrect period and a reliable period are set to the same length. While one window calculates correct values, another window calculates incorrect values thus to alternate the correct values and the incorrect values. An example of calculating a β metric using two windows is the beta metric calculation section 230 shown in FIG. 3. Therefore, a SISO decoder 48-2 in a window mode calculates three values of a α metric, a β1 metric and a β2 metric. A delta metric must be calculated before the three metrics are calculated.
Referring to FIG. 3, the delta metric calculators 211 to 213 receive data bits of a received signal stored in different addresses of the memory buffer 46-1, and calculate corresponding delta metrics. That is, the delta metric calculators 211 to 213, as illustrated in FIG. 7, read signals in different positions from the memory buffer 46-1 for a 1-clock time of an operating frequency for the turbo decoder.
FIG. 6 is a block diagram illustrating an example of a processing flow of a data bit input and a metric output by the SISO decoder shown in FIG. 3. Referring to FIG. 6, it is noted that data bits of a received signal stored in different addresses of the memory buffer 46-1 are applied to the delta metric calculators 211 to 213 of the SISO decoder 48-2. A horizontal line indicates a time axis, and it can be noted that different data bits are provided to the delta metric calculators 211 to 213 with the passage of time. For such an operation, the memory buffer 46-1 must be accessed three times faster than an operating frequency of the turbo decoder. That is, a clock three times faster than a turbo decoder clock must be used as a clock of the memory buffer 46-1.
FIG. 7 is a timing diagram illustrating an example of timing for a memory buffer access operation by the SISO decoder shown in FIG. 3. Referring to FIG. 7, the SISO decoder reads data bits data1, data2 and data3 stored in different addresses addr1, addr2 and addr3 of the memory buffer 46-1, and calculates a delta metric for an α metric, a delta metric for a β1 metric and a delta metric for a β2 metric. For that purpose, a read operation of the memory buffer 46-1 is performed at a rate three times faster than a turbo decoder clock.
A memory buffer access operation and a data processing operation illustrated in FIGS. 6 and 7 are performed on the assumption that a window size (or length) W is W=4 which is much shorter than an actually applied length. When actually applied to a high-speed (or high-rate) turbo decoder, the window size will be set to 24 to 48 (W=24˜28), and it can be set to a larger value according to circumstances. Although the window size W is changed, a structure of the buffer is not changed and the entire shape of a data flow diagram is also not changed, but increased in a ratio of a length.
Referring to FIG. 6, an alphabet written in each box of a delta block input represents data bits stored in different addresses of the memory buffer 46-1, and means a value applied to the delta metric calculator 210. When a β metric is first calculated as compared with an α metric, two β metric calculators 231 and 232 alternately operate (see FIG. 6 with reference to the T1 period and T2 period). An α metric is simultaneously calculated from a time when a reliable β1 metric is calculated (see T2 period). When a β metric is calculated, incorrect probability values are output for the beginning W period, but a metric value with reliable probability is output for the following W period. In an α output, a β1 output and a β2 output, an alphabet in each box means order of a metric. Since outputs of the delta metric calculators 212 and 213 for β1 and β2 alternate with each other, β metrics calculated by the beta metric calculators 231 and 232 are continuous. In FIG. 6, a circle shown by a dotted line indicates that data bits necessary at that time are received signals in different positions, or different addresses d, n and f of the memory buffer 46-1.
Meanwhile, if it is assumed that the SISO decoder shown in FIG. 3 is used for a 1×EV-DV system that requires a high data rate, a turbo decoder operating at a frequency of about 30 to 60 MHz is required. Therefore, an operating frequency of the memory buffer 46-1 must be determined within a 90 to 180 MHz range, which amounts to three times the operating frequency of a turbo decoder. Such an operating frequency of the turbo decoder is not appropriate for a mobile communication terminal that requires low power consumption.
As described above, the 1×EV-DV system, a typical 3rd generation mobile communication system, enables high-speed packet data communication. In such a communication system, a high-speed turbo decoder is required for high performance. For high-speed decoding, data bits (or symbols) stored in the memory buffer connected to a previous stage of the turbo decoder must be applied to the turbo decoder in an appropriate method. Compared with the SISO decoder with a frame mode scheme, the SISO decoder with a sliding window mode scheme can reduce an initial delay. Therefore, it is preferable to use the SISO decoder with a sliding window mode scheme as a turbo decoder. The SISO decoder with a sliding window mode scheme performs a decoding operation after reading data bits corresponding to the number of windows from the memory buffer. For example, if the number of windows is 2, the SISO decoder calculates metrics for decoding after reading data bits three times from the memory buffer. Such an operation raises no problem when the turbo decoder operates at a low rate, but it may raise a problem when the turbo decoder operates at a high rate. This is because when the memory buffer must operate three times faster than the turbo decoder and an operating frequency of the turbo decoder is low, using a memory buffer having a rate three times higher than the operating frequency is reasonable to a mobile communication terminal, but when an operating frequency of the turbo decoder is high, using a memory buffer having a rate three times higher than the operating frequency will be considerably unreasonable to the mobile communication terminal. For example, a turbo decoder for a CDMA2000 or UMTS system aimed at providing a high-speed data service must operate at a high rate in order to reach its full capability. In addition, if even an operating frequency of the memory buffer is increased, power consumed in the mobile communication terminal will be dramatically increased. The drastic increase in power consumption is not appropriate for the mobile communication terminal that requires low power design.